#define _CRT_SECURE_NO_WARNINGS
#include"sort.h"


void STInit(ST* ps) {
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STDestroy(ST* ps) {
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STPush(ST* ps, int x) {
	if (ps->top == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		int* tmp = (int*)realloc(ps->data, sizeof(int) * newcapacity);
		if (tmp == NULL) {
			perror("realloc failed");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps) {
	ps->top--;
}
int STTop(ST* ps) {
	return ps->data[ps->top - 1];
}
int STEmpty(ST* ps) {
	if (ps->top == 0) {
		return 1;
	}
	return 0;
}
void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int exchange = 0;
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				exchange = 1;
				Swap(&a[j], &a[j + 1]);
			}
		}
		if (exchange == 0) {
			break;
		}
	}
}

void InsertSort(int* a, int n) {
	for (int i = 1; i < n; i++) {
		int tmp = a[i];
		int end = i - 1;
		while (end >= 0) {
			if (tmp < a[end]) {
				a[end + 1] = a[end];
			}
			else {
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}

void SelectSort(int* a, int n) {
	int left = 0;
	int right = n - 1;
	while (left < right) {
		int mini = left;
		int maxi = left;
		for (int i = left; i <= right; i++) {
			if (a[i] > a[maxi]) {
				maxi = i;
			}
			if (a[i] < a[mini]) {
				mini = i;
			}
		}
		Swap(&a[mini], &a[left]);
		if (maxi == left) {
			maxi = mini;
		}
		Swap(&a[maxi], &a[right]);
		left++;
		right--;
	}
}


//void ShellSort(int* a, int n) {
//	int gap = n / 2;
//	while (gap >= 1) {
//		for (int i = 0; i < n - gap; i++) {
//			int tmp = a[i + gap];
//			int end = i;
//			while (end >= 0) {
//				if (tmp < a[end]) {
//					a[end + gap] = a[end];
//				}
//				else {
//					break;
//				}
//				end -= gap;
//			}
//			a[end + gap] = tmp;
//		}
//		gap /= 2;
//	}
//}
void ShellSort(int* a, int n) {
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = gap; i < n ; i++) {
 			int tmp = a[i];
			int end = i-gap;
			while (end >= 0) {
				if (tmp < a[end]) {
					a[end + gap] = a[end];
				}
				else {
					break;
				}
				end -= gap;
			}
			a[end + gap] = tmp;
		}
	}
}


//void AdjustDown(int* a, int sign, int n)
//{
//	int up = sign;
//	int down = sign * 2 + 1;
//	while (down < n) {
//		if (down + 1 < n && a[down + 1] > a[down]) {
//			down++;
//		}
//		if (a[up] < a[down]) {
//			Swap(&a[up], &a[down]);
//			
//		}
//		up = down;
//		down = down * 2 + 1;
//		
//	}
//}
//void HeapSort(int* a, int n) {
//	for (int i = (n - 2) / 2; i >= 0; i--) {
//		AdjustDown(a, i, n);
//	}
//	for (int i = 0; i < n - 1; i++) {
//		Swap(&a[0], &a[n - 1 - i]);
//		AdjustDown(a, 0, n - i-1);
//	}
//}
void AdjustDown(int* a, int ret, int n) {
	int parent = ret;
	int child = ret * 2 + 1;
	while (child < n) {
		if (child+1<n&&a[child] < a[child + 1]) {
			child++;
		}
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
		}
		else {
			break;
		}
		parent = child;
		child = child * 2 + 1;
	}
}
void HeapSort(int* a, int n) {
	for (int i = (n - 2) / 2; i >= 0; i--) {
		AdjustDown(a, i, n);
	}
	for (int i = 0; i < n - 1; i++) {
		Swap(&a[0], &a[n - 1 - i]);
		AdjustDown(a, 0, n - i-1);
	}
}


//void CountSort(int* a, int n) {
//	int min = a[0];
//	int max = a[0];
//	for (int i = 0; i < n; i++) {
//		if (a[i] < min) {
//			min = a[i];
//		}
//		if (a[i] > max) {
//			max = a[i];
//		}
//	}
//	int num = max - min + 1;
//	int* tmp = (int*)calloc(num,sizeof(int));
//	if (tmp == NULL) {
//		perror("calloc failed");
//		exit(-1);
//	}
//	for (int i = 0; i < n; i++) {
//		tmp[a[i] - min]++;
//	}
//	int j = 0;
//	for (int i = 0; i < n; i++) {
//		while (tmp[j] == 0) {
//			j++;
//		}
//		while (tmp[j]!=0&&tmp[j]--) {
//			a[i] = j + min;
//		}
//	}
//}

void CountSort(int* a, int n) {
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++) {
		if (a[i] > max) {
			max = a[i];
		}
		if (a[i] < min) {
			min = a[i];
		}
	}
	int num = max - min + 1;
	int* tmp = (int*)malloc(sizeof(int) * num);
	if (tmp == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	memset(tmp, 0, sizeof(int) * num);
	for (int i = 0; i < n; i++) {
		tmp[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < num; i++) {
		while (tmp[i]--) {
			a[j++] = i + min;
		}
	}

	//int j = 0;
	//int k = 0;
	//while (1) {
	//	while (tmp[j] == 0) {
	//		j++;
	//	}
	//	if (j >= num) {
	//		break;
	//	}
	//	a[k] = j + min;
	//	k++;
	//	tmp[j]--;
	//}
	/*while (j < num) {
		while (tmp[j] == 0) {
			j++;
		}
		a[k] = j + min;
		k++;
		tmp[j]--;
	}*/
}


void QuickSort1(int* a, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int tmp = a[begin];
	int left = begin;
	int right = end;
	while (left < right) {
		while (a[right] >= tmp&&left<right) {
			right--;
		}
		while (a[left] <= tmp&&left<right) {
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[begin]);
	QuickSort1(a, begin, left - 1);
	QuickSort1(a, left + 1, end);
}

void QuickSort2(int* a, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int tmp = a[begin];
	int pit = begin;
	int left = begin;
	int right = end;
	while (left < right) {
		while (left < right && a[right] >= tmp) {
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while (left < right && a[left] <= tmp) {
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[pit] = tmp;
	QuickSort2(a, begin, pit - 1);
	QuickSort2(a, pit+1, end);
}


void QuickSort3(int* a, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int tmp = a[begin];
	int left = begin;
	int right = begin;
	while (right <= end) {
		if (tmp > a[right]&&++left!=right) {
			Swap(&a[left], &a[right]);
		}
		right++;
	}
	Swap(&a[begin], &a[left]);
	QuickSort3(a, begin, left - 1);
	QuickSort3(a, left + 1, end);
}

void QuickSortNONR(int* a, int begin, int end) {
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);
	while (!STEmpty(&st)) {
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);
		int l = left;
		int r = right;
		int tmp = a[l];
		while (l < r) {
			while (l < r && a[r] >= tmp) {
				r--;
			}
			while (l < r && a[l] <= tmp) {
				l++;
			}
			Swap(&a[l], &a[r]);
		}
		Swap(&a[l], &a[left]);
		if (left < l - 1) {
			STPush(&st, l - 1);
			STPush(&st, left);
			if (l + 1 < right) {
				STPush(&st, right);
				STPush(&st, l + 1);
		}
		}
	}

}


void Merge_Sort(int* a, int* tmp, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int mid = (begin + end) / 2;
	Merge_Sort(a, tmp, begin, mid);
	Merge_Sort(a, tmp, mid + 1, end);
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int cur = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			tmp[cur++] = a[begin1++];
			
		}
		else {
			tmp[cur++] = a[begin2++];
		
		}
	}
	while (begin1 <= end1) {
		tmp[cur++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[cur++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	Merge_Sort(a, tmp, 0, n - 1);
}

void MergeSortNONR(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n) {
		gap *= 2;
		for (int i = 0; i < n; i += gap) {
			int begin1 = i;
			int end1 = i + gap / 2 - 1;

			int begin2 = i + gap / 2;

			int end2 = i + gap - 1;
 			if (begin2 >= n) {
				break;
			}
			if (end2 >= n) {
				end2 = n - 1;
			}
			int cur = begin1;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] < a[begin2]) {
					tmp[cur++] = a[begin1++];
				}
				else {
					tmp[cur++] = a[begin2++];
				}

			}
			while (begin1 <= end1) {
				tmp[cur++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[cur++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i+1));
		}
	}
}
